package com.leetcode.list;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * date:
 * description:
 */
public class LFUCache {

    private int minfreq;
    private int capacity;
    private Map<Integer, Node> keyMap;
    private Map<Integer, LinkedList<Node>> freqMap;

    public LFUCache(int capacity) {
        minfreq = 0;
        this.capacity = capacity;
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
    }

    public int get(int key){
        if(!keyMap.containsKey(key)){
            return -1;
        }
        Node target = keyMap.get(key);
        int val = target.getValue();
        freqMap.get(target.getFreq()).remove(target);
        if(freqMap.get(target.getFreq()).size() == 0){
//            minfreq++;
            if(minfreq == target.getFreq()){
                minfreq++;
            }
        }
        target.incrFreq();
        if(!freqMap.containsKey(target.getFreq())){
            freqMap.put(target.getFreq(), new LinkedList<Node>());
        }
        freqMap.get(target.getFreq()).offerFirst(target);
        return val;
    }

    public void put(int key, int value){
        if(capacity == 0){
            return;
        }
        if(keyMap.containsKey(key)){
            Node target = keyMap.get(key);
            freqMap.get(target.getFreq()).remove(target);
            if(freqMap.get(target.getFreq()).size() == 0){
                minfreq++;
            }
            target.incrFreq();
            target.setValue(value);
            if(!freqMap.containsKey(target.getFreq())){
                freqMap.put(target.getFreq(), new LinkedList<Node>());
            }
            freqMap.get(target.getFreq()).offerFirst(target);
        }else{
            Node inserted = new Node(key, value, 1);
            if(keyMap.size() == capacity){
                Node deleted = freqMap.get(minfreq).pollLast();
                keyMap.remove(deleted.getKey());
            }
            minfreq = 1;
            keyMap.put(key, inserted);
            if(!freqMap.containsKey(inserted.getFreq())){
                freqMap.put(inserted.getFreq(), new LinkedList<Node>());
            }
            freqMap.get(inserted.getFreq()).offerFirst(inserted);
        }
    }

    private static class Node{
        private int key;
        private int value;
        private int freq;

        public Node(){}

        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }

        public void incrFreq(){
            this.freq++;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public int getFreq() {
            return freq;
        }

        public void setFreq(int freq) {
            this.freq = freq;
        }
    }

}
